開催案内

多変数多項式暗号の紹介

日時

2025年8月4日（月）16:45〜18:15

開催場所

理学研究科5号館525号室(別名：第4講義室)

講師

池松 泰彦 氏（九州大学 マス・フォア・インダストリ研究所 准教授）

概要

量子計算機に耐性のある暗号として多変数多項式暗号が研究されている。この暗号は有限体上の二次連立方程式の求解困難性を利用して構成される。本講演では、有力な方式であるUOVを中心に多変数多項式暗号の構成やその安全性解析について紹介する。

備考

◎itami.masato.7u ＊ kyoto-u.ac.jp（＊を@に変えてください）

活動報告

九州大学マス・フォア・インダストリ研究所の池松泰彦さんに「多変数多項式暗号の紹介」というタイトルで講演していただきました。

講演は多変数多項式暗号のレビューから始まりました。多変数多項式暗号（MPKC）とは、多変数二次多項式問題（MQ問題）の求解困難性を利用した暗号技術のことです。公開鍵暗号基盤として現在利用されているRSA暗号や楕円曲線暗号は、量子計算機で実装可能なShorのアルゴリズムによって危殆化してしまうため、量子計算機を用いても破ることのできない暗号(耐量子計算機暗号)の開発が進んでおり、多変数多項式暗号もその有力な候補の1つになっているそうです。講演では、二次中心写像を用いたMPKC署名の一般的構成について解説していただきました。また、具体例として、1988年に松本–今井によって提案された初のMPKCの概略と、それが1995年にPatarinのLinearization attackで破られたことについても説明していだきました。

続いて、MPKCの1種であるUnbalanced Oil & Vinegar (UOV)署名方式について解説していただきました。UOVでは、vinegar変数とoil変数の2種類を用意し、oil変数に関しては連立1次方程式系となるように選ぶことで、連立二次方程式系の求解を容易にするというのが基本的なアイデアです。UOVは他の耐量子計算機暗号と比べて公開鍵サイズが大きいという欠点があるため、いくつかの改良版が作られています。池松さんも開発に携わっている、剰余環の構造を利用して公開鍵サイズを削減したQR-UOVを含め、いくつかの改良方法についても解説していただきました。

最後に、MQ問題を解く代表的な方法の1つであるXLアルゴリズムについて説明していただきました。XLアルゴリズムは、変数の積を新しい変数とみなすことによって多変数二次多項式系からより多変数の一次方程式系を作り、その一次方程式系の解を利用して元の多変数二次多項式系の解を探す手法です。多変数一次方程式を作る際に、多項式の適切な次数をどう選べば良いのかは自明ではありません。この次数を二次方程式系のHilbert級数を使って予想する研究を紹介していただきました。

講演中も講演後も多くの質問が出て、UOVの攻撃方法などに関して活発な議論が行われました。 （文責：伊丹將人）